The invention relates in general to data packet filtering. In particular the invention relates to such a method as specified in the preamble of the independent claims.
Public networks are presently being used more and more for sensitive and mission critical communications and the internal networks of various organisations and enterprises are nowadays connected to the public networks, Internet being one of them. Since the basic mechanisms of the public networks were originally not designed with secrecy and confidentiality in mind, public networks are untrusted networks. To protect an internal network, a special network element is usually used to connect the internal network to a public network. This special network element is often called a security gateway or a firewall, and the purpose of a such network element is to prevent unauthorised access to the internal network. Typically there is need to restrict access to an internal network from a public network and/or to restrict access from the internal network to the public network or further networks connected to the public network. On data packet level this means that data packets, which are entering and/or exiting the internal network, are screened or filtered in a network element in order to determine whether the data packets are allowed to traverse the network element or not.
Data packet filtering may be needed for other purposes, too. For example, in intrusion detection systems (IDS) the traffic (data packets) flowing in a network is monitored and analysed. On the basis of the type of the data packet different kind of analysis may be conducted. Therefore, data packets need to be filtered in order to determine what kind of analysis is required.
FIG. 1 illustrates an example network topology with a first internal network 12, a second internal network 14 and a public network 10. The public network may be, for example, the Internet. The internal networks 12, 14 are connected to the public network 10 via network elements 16 and 18, respectively, the network elements 16 and 18 being firewalls or security gateways. Additionally, there is a network element 20 connected to the internal network 14. The network element 20 is an IDS node, which monitors the data packets entering and exiting the internal network 14. A network element 16, 18, 20 may be implemented as one network node or as a cluster of network nodes.
The term network element is used in this description for referring to any network element or to a cluster of any network elements, in which data packet filtering is performed. A network element may be, for example, a firewall node, a firewall node provided with Virtual Private Network (VPN) functionality, a network monitoring node, an IDS node.
The data packet filtering is usually done by means of a rule base comprising a set of rules. Each rule comprises certain parameters of data packets (e.g. source address, destination address and protocol) and an action (i.e. information about how to handle the data packet corresponding to the parameters of the rule). In a firewall, the action is typically ‘drop’ or ‘accept’, which means the data packet is discarded or allowed to proceed, correspondingly. Such a set of rules is usually sequentially ordered and each received data packet is compared with the rules linearly, one by one, until a match is found. The first rule, whose parameters match the parameters of the received data packet, is applied to the data packet and the data packet is handled as indicated by the rule. Sometimes the action of the rule can be “continue”, which means that further matching rules need to be inspected to find out how the packet shall be handled. The action may also be instructions to run some script, when a data packet matches the rule. A data packet, whose parameters do not match any rule, may be for example discarded. FIG. 2 illustrates as an example a rule base, having a first rule Rule1, a second rule Rule2, and so forth. Each rule has two parameter fields, field1 and field2, and an action field. In many practical applications, there are more than two parameter fields, though.
Considering the performance of the network element it is important that the matching of the data packets to the rule base is done as efficiently as possible. Especially, if the rule base is large, the performance of the network element depends on the matching speed. In many cases, appropriate functionality of the network element requires a large rule base. Additionally, it may be required to translate some user defined higher level rules to lower level rules before matching can take place (e.g. a collection of of 20 IP-addresses defined in one higher level rule may need to be translated to 20 separate lower level rules). Furthermore, a packet is often compared to large number of rules before the rule to which it matches is found. In the worst case, a packet is compared to all rules in the rule base and then discarded or the packet matches the very last rule. This results in inefficient use of processing resources in the network element, if linear matching is used.
In European patent application EP 1 006 701 A2, “Adaptive re-ordering of data packet filter rules”, by Krishnan P, Raz D and Sugla B, a method for re-ordering filter rules is presented for improving the matching process. The rules are re-ordered so that a rule that most frequently matching rules are arranged to be as close to the beginning of the rule base as possible. The disadvantage in this solution is that in order to maintain the correct functionality of the rule base changing the order of the rules is limited. Additionally, if the data packets to be handled are not homogenous, the proposed solution does not improve the matching process, since the re-ordering is based on the history of processed data packets.
Thus, a more efficient method for data packet filtering is required, especially in connection with large rule bases.